/*
    libnbds
    Non-blocking Data Structures Library

    Copyright (C) 2011 Paweł Dziepak

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#include "atomic.h"
#include "fifo.h"

using namespace nbds;

void fifo_base::enqueue_(void *obj) {
	elem *x = new elem;
	x->obj = obj;
	x->prev = NULL;

	elem *old_first;
	do {
		old_first = arch::get(&first);
		hp.set(old_first);
	} while (arch::cmp_and_swp(&first, old_first, x) != old_first);
	
	if (!old_first)
		arch::xchg(&last, x);
	else {
		if (arch::cmp_and_swp(&old_first->prev, (elem*)0, x)
							== (elem*)arch::max_ptr)
			arch::xchg(&last, x);
	}

	hp.release();
}

void *fifo_base::dequeue_() {
	elem *prev = NULL;
	elem *old_last = NULL;

	do {
		do {
			old_last = arch::get(&last);
			hp.set(old_last);
		} while (arch::get(&last) != old_last);

		if (!old_last)
			return NULL;

		prev = arch::get(&old_last->prev);
	} while (arch::cmp_and_swp(&last, old_last, prev) != old_last);

	if (!prev) {
		if (arch::cmp_and_swp(&first, old_last, (elem*)0) != old_last) {
			if (arch::cmp_and_swp(&old_last->prev, (elem*)0,
					(elem*)arch::max_ptr) != NULL)
				arch::xchg(&last, old_last->prev);
		}
	}

	void *obj = old_last->obj;
	hp.retire(old_last);

	return obj;
}
